package com.company;

import java.util.*;

public class LRUCache<K, V> {

    private final int MAX_CACHE_SIZE;

    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> pre;
        Entry<K, V> next;
    }

    /**
     * 我这里是最新的cache
     * 而 LinkedHashMap 中是 eldest
     * The head (eldest) of the doubly linked list.
     */
    private Entry<K, V> head;
    /**
     * 我这里是最老的cache
     * The tail (youngest) of the doubly linked list.
     */
    private Entry<K, V> tail;
    private final Map<K, Entry<K, V>> map;

    public LRUCache(int max_cache_size) {
        MAX_CACHE_SIZE = max_cache_size;
        map = new HashMap<>(max_cache_size);
    }

    public synchronized void put(K key, V value){
        Entry<K, V> entry = getEntry(key);
        if (entry == null){
            if (map.size() >= MAX_CACHE_SIZE){
                // 缓存满, 删除最后一组元素
                map.remove(head.key);
                removeTail();  //删除队列的最后元素
            }
            entry = new Entry<>();
            entry.key = key;
        }
        entry.value = value;
        moveToHead(entry);
        map.put(key, entry);
    }

    public synchronized V get(K key){
        Entry<K, V> entry = getEntry(key);
        if (entry == null) return null;
        // 移动到前面
        moveToHead(entry);
        return entry.value;
    }

    private Entry<K, V> getEntry(K key){
        return map.get(key);
    }

    public synchronized void remove(K key){
        Entry<K, V> entry = getEntry(key);
        if (entry == null) return;
        if (entry.pre != null) entry.pre.next = entry.next;
        if (entry.next != null) entry.next.pre = entry.pre;
        if (entry == head) head = entry.pre;
        if (entry == tail) tail = entry.next;
        map.remove(key);
    }

    private void moveToHead(Entry<K,V> entry) {
        // 将数据移动到双向链表的 head
        if (head == null || tail == null){
            head = tail = entry;
            return;
        }
        if (entry == head) return;
        // 断开 entry
        if (entry.next != null) entry.next.pre = entry.pre;
        if (entry.pre != null) entry.pre.next = entry.next;
        // 如果是 tail, 还需修改这个指针
        if (entry == tail) tail = tail.next;
        // 插入 head
        entry.pre = head;
        entry.next = null;
        head.next = entry;
        head = entry;
    }

    private void removeTail(){
        // 移除最久放入缓存中的数据
        if (tail == null) return;
        // 修改双向指针
        if (tail.next != null)  tail.next.pre = tail.pre;
        if (tail.pre != null)  tail.pre.next = tail.next;
        // 修改 tail 的指向
        tail = tail.next;
    }

    public void traverse(){
        Entry<K, V> node = tail;
        while (node != null){
            System.out.printf("%d ", node.value);
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args){
        LRUCache<Integer, Integer> cache = new LRUCache<>(5);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 4);
        cache.traverse();

        cache.put(5, 5);
        cache.put(6, 6);
        cache.traverse();

        cache.remove(3);
        cache.traverse();

        cache.remove(2);
        cache.traverse();

        cache.get(4);
        cache.traverse();

        LinkedHashMap<Integer, Integer> linkedCache = new LinkedHashMap<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        new ArrayList<Integer>().toArray();
    }

}
